package com.peng.leetcode.array;

/**
 * SearchMatrix
 * <p>
 * 74. 搜索二维矩阵
 *
 * @author: lupeng6
 * @create: 2021/3/19 14:01
 */
public class SearchMatrix {

    public static void main(String[] args) {
        int[][] matrix = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        new SearchMatrix().searchMatrix(matrix, 3);
    }


    public boolean searchMatrix(int[][] matrix, int target) {
        int col = matrix[0].length;
        int left = 0;
        int right = matrix.length * col;

        while (left <= right) {
            int mid = (left + right) / 2;
            int row = mid / col;
            int colIndex = mid % col;
            if (matrix[row][colIndex] == target) {
                return true;
            } else if (matrix[row][colIndex] > target) {
                right = (row * col + colIndex) - 1;
            } else if (matrix[row][colIndex] < target) {
                left = (row * col + colIndex) + 1;
            }
        }

        return false;
    }

}
